package com.feng.designpattern.strategy.sortarray;

/**
 * @author Administrator
 * 插入法排序：
 * 它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张
 *
 * 例:有数组 n[]={2,6,7,9},用插入法排序,i>0,j>0,temp=n[i]
 *     外循环第一轮:i=1;j=1; 比较 n[j-1]=3 与 temp =6; temp > n[j-1] => 交换n[j]=n[j-1] => 6279;j=0,break跳出,进入第二轮
 *     外循环第二轮:i=2;j=2;内循环第一轮:=>6729
 *            内循环第二轮:=>7629
 *     外循环第三轮:i=3;j=3;内循环第一轮:=>7692
 *            内循环第二轮:=>7962
 *            内循环第三轮:=>9762 <=> 排序完毕   时间复杂度为O(N)=O(4)
 *            
 * 
插入法:

遍历排序集合，每到一个元素时，都要将这个元素与所有它之前的元素遍历比较一遍，让符合排序顺序的元素挨个移动到当前范围内它最应该出现的位置。交换是相邻遍历移动，双重循环控制实现.这种排序法属于地头蛇类型,在我的地牌上我要把所有的东西按一定的顺序规整,过来一个,规整一个.

处理代码如下:

public static int[] insertSort(int[] data) {
   int temp;
   for (int i = 1; i < data.length; i++) {
    for (int j = i; (j > 0) && (data[j] > data[j - 1]); j--) {

     temp = data[j];
     data[j] = data[j - 1];
     data[j - 1] = temp;
    }
   }
   return data;
}
 */
public class InsertionSort extends SortStrategy {
	public void sort(int[] data) {
		// 插入排序法(Insertion Sort)
		long begin = System.currentTimeMillis();
		for (int k = 0; k < 1000000; k++) {
			for (int i = 1; i < data.length; i++) {
				int j = i;
				while (data[j - 1] < data[i]) {
					data[j] = data[j - 1];
					j--;
					if (j <= 0) {
						break;
					}
				}
				data[j] = data[i];
			}
		}
		long end = System.currentTimeMillis();
		System.out.println("插入法用时为：" + (end - begin));
		// 打印排序好的结果
		for (int i = 0; i < data.length; i++) {
			System.out.println(data[i]);
		}
	}
}
